package com.mingqi.hw.test;


import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
/*3.1 前序遍历二叉树
        给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
        3
        / \
        9 20
        / \
        15 7
        输出 3,9,20,15,7*/
public class ZT03 {
    static class Node {
        public Node(int num) {
            this.num = num;
        }
        public int num;
        public Node left;
        public Node right;
    }
    static AtomicInteger indexA = new AtomicInteger();
    static List<Map<Integer, List<Integer>>> list = new ArrayList<>();
    public static void main(String[] args) {
        Node root = getNodeTree();
        int level = 1;
        indexA.set(1);
        printNode(root, indexA, level);
        System.out.println("-------------------------------");
        list.stream().forEach(map-> System.out.println(map));
    }
    private static Node getNodeTree() {
        //level1
        Node root = new Node(1);
        //level2
        Node left2 = new Node(2);
        Node right2 = new Node(3);
        root.left = left2;
        root.right = right2;//level3
        Node left2_left3 = new Node(4);
        Node left2_right3 = new Node(5);
        left2.left = left2_left3;
        left2.right = left2_right3;
        Node right2_left3 = new Node(6);
        Node right2_right3 = new Node(7);
        right2.left = right2_left3;
        right2.right = right2_right3;
        //leve4
        Node left2_left3_left4 = new Node(8);
        Node left2_left3_right4 = new Node(9);
        left2_left3.left = left2_left3_left4;
        left2_left3.right = left2_left3_right4;

        Node left2_right3_left4 = new Node(10);
        Node left2_right3_right4 = new Node(11);
        left2_right3.left = left2_right3_left4;
        left2_right3.right = left2_right3_right4;

        Node right2_left3_left4 = new Node(12);
        Node right2_left3_right4 = new Node(13);
        right2_left3.left = right2_left3_left4;
        right2_left3.right = right2_left3_right4;

        Node right2_right3_left4 = new Node(14);
        Node right2_right3_right4 = new Node(15);
        right2_right3.left = right2_right3_left4;
        right2_right3.right = right2_right3_right4;
        return root;
    }


    /**
     * @param node
     * @param indexA
     * @param level
     */
    public static void printNode(Node node, AtomicInteger indexA, int level) {
        if (node != null) {
            if (list.size() < level) {
                Map<Integer, List<Integer>> map = new HashMap<>();
                map.put(level, new ArrayList<>());
                list.add(map);
            }
            list.get(level - 1).get(level).add(node.num);
            System.out.println(node.num + "\t\t\t" + indexA.get() + "\t\t\t" + level);
            indexA.incrementAndGet();

        }
        level++;
        if (node.left != null) {
            printNode(node.left, indexA, level);
        }
        if (node.right != null) {
            printNode(node.right, indexA, level);
        }
    }
    public List<List<Integer>> levelOrder1(TreeNode root) {
         /*迭代-广度优先搜索
         利用队列的先进先出特性按序保存每层节点
         时间复杂度O(n),空间复杂度O(n)
         * */
        if (root == null)
            return new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        //queue 初始时为 [root] ，代表第 1 层
        queue.add(root);
        while (!queue.isEmpty()) {
            //关键：count保存要处理的这一层的节点个数
            int count = queue.size();
            //list保存此层的所有节点值
            List<Integer> list = new ArrayList<Integer>();
            //这个while循环保证已处理的旧层的节点全部出去，待处理的新层节点全部进入
            while (count > 0) {
                //当前层的节点逐个出列
                TreeNode node = queue.poll();
                //保存此元素的值
                list.add(node.val);
                //存在左孩子则左孩子进队列（下层节点）
                if (node.left != null)
                    queue.add(node.left);
                //存在右孩子则右孩子进队列（下层节点）
                if (node.right != null)
                    queue.add(node.right);
                count--;
            }
            res.add(list);
        }
        return res;
    }
    //////////////////////////////////////
    List<List<Integer>> result = new ArrayList<>();
    //1.DFS 将每一次用k记录 添加到对应的层级
// time :O(n)
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)    return result;
        recur(root,0);
        return result;
    }

    private void recur(TreeNode root,int k){
        if(root != null){
            if(result.size()<=k){
                result.add(new ArrayList<>());
            }
            result.get(k).add(root.val);
            recur(root.left,k+1);
            recur(root.right,k+1);
        }
    }
    //2.BFS 层序遍历 将每层节点添加到queue中
    public List<List<Integer>> levelOrder22(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null)    return result;
        Queue<TreeNode> queue = new LinkedList<>();

        //1.添加首节点
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt = queue.size();
            List<Integer> list = new ArrayList<>();
            while(cnt-->0){
                TreeNode node = queue.poll();
                if(node == null){
                    continue;
                }
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if(queue.size()!=0){
                result.add(list);
            }
        }
        return result;
    }

    // Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<List<Integer>> levelOrderNew(TreeNode root) {
         /*递归··深度优先搜索
         时间复杂度O(n),空间复杂度O(h)（二叉树高度）
         * */
        if (root == null) {
            return new ArrayList<List<Integer>>();
        }
        //用来存放最终结果
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(1, root, res);
        return res;
    }

    void dfs(int index, TreeNode root, List<List<Integer>> res) {
         /*递归函数定义，层序遍历以root为根的二叉树的节点（root处于第index层）
         结果保存到res
         * */
        //假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
        if (res.size() < index) {
            res.add(new ArrayList<Integer>());
        }
        //1.先把root节点值添加到res[index-1]数组里
        //将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
        //res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
        res.get(index - 1).add(root.val);
        //2.再递归的处理左子树，右子树，同时将层数index+1
        if (root.left != null) {
            dfs(index + 1, root.left, res);
        }
        if (root.right != null) {
            dfs(index + 1, root.right, res);
        }
    }
}
//1			1			1
//2			2			2
//4			3			3
//8			4			4
//9			5			4
//5			6			3
//10			7			4
//11			8			4
//3			9			2
//6			10			3
//12			11			4
//13			12			4
//7			13			3
//14			14			4
//15			15			4
//-------------------------------
//{1=[1]}
//{2=[2, 3]}
//{3=[4, 5, 6, 7]}
//{4=[8, 9, 10, 11, 12, 13, 14, 15]}